Let X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = Σ 1 2 , graphs. If X = Y = ω ω , P may be taken to be Π 1 1 . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P (...) can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy. (shrink)

We survey some results and problems arising from a classic problem of Steinhaus: Is there a subset S of R 2 such that each isometric copy of mathbbZ 2 (the lattice points in the plane) meets S in exactly one point.

It is known that the box dimension of any Martin-Löf random closed set of ${\{0,1\}^\mathbb{N}}$ is ${\log_2(\frac{4}{3})}$ . Barmpalias et al. [J Logic Comput 17(6):1041–1062, 2007] gave one method of producing such random closed sets and then computed the box dimension, and posed several questions regarding other methods of construction. We outline a method using random recursive constructions for computing the Hausdorff dimension of almost every random closed set of ${\{0,1\}^\mathbb{N}}$ , and propose a general method for random closed sets (...) in other spaces. We further find both the appropriate dimensional Hausdorff measure and the exact Hausdorff dimension for such random closed sets. (shrink)